package me.algo.str;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Objects;
import java.util.Set;
import java.util.function.Function;
import java.util.stream.Collectors;

/**
 * @author guozheng
 * @date 2024/4/22
 */
public class S2 {

    /**
     * 344. 反转字符串
     * @param s
     */
    public static void reverseString(char[] s) {
        if (Objects.isNull(s)) {
            return;
        }
        int left = 0;
        int right = s.length - 1;
        while (left < right) {
            char tmp = s[left];
            s[left] = s[right];
            s[right] = tmp;
            left++;
            right--;
        }
    }



    /**
    345. 反转字符串中的元音字母
     * @param s
     * @return
     */
    public static String reverseVowels(String s) {
        if (Objects.isNull(s) || s.length() == 0) {
            return s;
        }
        HashSet<Character> vs = new HashSet<>();
        vs.add('A');
        vs.add('E');
        vs.add('I');
        vs.add('O');
        vs.add('U');
        char[] array = s.toCharArray();
        int left = 0;
        int right = s.length() - 1;
        boolean m = false;
        while (left < right) {
            char lc = array[left];
            char rc = array[right];
            if (vs.contains(Character.toUpperCase(lc)) && !vs.contains(Character.toUpperCase(rc)) && !m) {
                right--;
                continue;
            }
            if (!vs.contains(Character.toUpperCase(lc)) && vs.contains(Character.toUpperCase(rc)) && !m) {
                left++;
                continue;
            }
            if (vs.contains(Character.toUpperCase(lc)) && vs.contains(Character.toUpperCase(rc))) {
                array[left] = rc;
                array[right] = lc;
            }
            left++;
            right--;
        }
        return String.valueOf(array);
    }


    /**
     * 67. 二进制求和
     * @param a
     * @param b
     * @return
     */
    public static String addBinary(String a, String b) {
        StringBuilder builder = new StringBuilder();
        if (Objects.isNull(a)) {
            return b;
        }
        if (Objects.isNull(b)) {
            return a;
        }
        int alen = a.length();
        int blen = b.length();
        int next = 0;
        for (int i = 0; i < Math.max(alen, blen); i++) {
            int aval = getNum(a, i);
            int bval = getNum(b, i);
            int i1 = aval + bval + next;
            int v = i1 % 2;
            next = i1 / 2;
            builder.append(v);
        }
        if (next != 0) {
            builder.append(next);
        }
        return builder.reverse().toString();
    }

    private static int getNum(String str, int index) {
        int length = str.length();
        if (index < length) {
            char c = str.charAt(length - 1 - index);
            return Integer.valueOf(String.valueOf(c));
        }
        return 0;
    }


    /**
     * 338. 比特位计数
     * 对于所有的数字，只有两类：
     *
     * 奇数：二进制表示中，奇数一定比前面那个偶数多一个 1，因为多的就是最低位的 1。
     *           举例：
     *          0 = 0       1 = 1
     *          2 = 10      3 = 11
     * 偶数：二进制表示中，偶数中 1 的个数一定和除以 2 之后的那个数一样多。因为最低位是 0，除以 2 就是右移一位，也就是把那个 0 抹掉而已，所以 1 的个数是不变的。
     *            举例：
     *           2 = 10       4 = 100       8 = 1000
     *           3 = 11       6 = 110       12 = 1100
     * 另外，0 的 1 个数为 0，于是就可以根据奇偶性开始遍历计算了。
     *
     * @param n
     * @return
     */
    public int[] countBits(int n) {
        int[] rtn = new int[n + 1];
        rtn[0] = 0;
        for (int i = 0; i <= n; i++) {
            if (i % 2 == 1) {
                rtn[i] = rtn[i - 1] + 1;
            } else {
                rtn[i] = rtn[i / 2];
            }
        }
        return rtn;
    }

    /**
     * 349. 两个数组的交集
     * @param nums1
     * @param nums2
     * @return
     */
    public static int[] intersection(int[] nums1, int[] nums2) {
        if (Objects.isNull(nums1) || Objects.isNull(nums2)) {
            return new int[0];
        }
        HashSet<Integer> set = new HashSet<>();
        for (int num : nums1) {
            set.add(num);
        }
        Set<Integer> rtn = new HashSet<>();
        for (int num : nums2) {
            if (set.contains(num)) {
                rtn.add(num);
            }
        }
        return rtn.stream().mapToInt(Integer::intValue).toArray();
    }

    /**
     * 350. 两个数组的交集 II
     * @param nums1
     * @param nums2
     * @return
     */
    public int[] intersect(int[] nums1, int[] nums2) {
        if (Objects.isNull(nums1) || Objects.isNull(nums2)) {
            return new int[0];
        }
        Map<Integer, Long> map1 = toMap(nums1);
        Map<Integer, Long> map2 = toMap(nums2);
        HashMap<Integer, Long> map = new HashMap<>();
        for (Map.Entry<Integer, Long> entry : map1.entrySet()) {
            Integer key = entry.getKey();
            if (map2.containsKey(key)) {
                Long v1 = entry.getValue();
                Long v2 = map2.get(key);
                long min = Math.min(v1, v2);
                map.put(key, min);
            }
        }
        return map.entrySet().stream().flatMap(v -> {
            Long repeated = v.getValue();
            Integer val = v.getKey();
            ArrayList<Integer> vals = new ArrayList<>();
            while (repeated > 0) {
                vals.add(val);
                repeated--;
            }
            return vals.stream();
        }).mapToInt(Integer::intValue).toArray();
    }

    private static Map<Integer, Long> toMap(int[] nums2) {
        return Arrays.stream(nums2)
                .mapToObj(Integer::valueOf)
                .collect(Collectors.groupingBy(Function.identity(), Collectors.counting()));
    }

    /**
     * 1002. 查找共用字符
     * @param words
     * @return
     */
    public static List<String> commonChars(String[] words) {
        if (Objects.isNull(words)) {
            return new ArrayList<>();
        }
        Map<Character, Long> counts = null;
        for (String word : words) {
            char[] array = word.toCharArray();
            Map<Character, Long> mapCount = toMap(array);
            if (counts == null) {
                counts = mapCount;
                continue;
            } else {
                Map<Character, Long> minMap = new HashMap<>();
                for (Map.Entry<Character, Long> entry : mapCount.entrySet()) {
                    Character character = entry.getKey();
                    if (counts.containsKey(character)) {
                        Long v1 = entry.getValue();
                        Long v2 = counts.get(character);
                        minMap.put(character, Math.min(v1, v2));
                    }
                }
                counts = minMap;
            }
        }
        if (Objects.isNull(counts)) {
            return new ArrayList<>();
        }
        return counts.entrySet().stream()
                .flatMap(ent -> {
                    List<Character> rt = new ArrayList<>();
                    Long value = ent.getValue();
                    while (value > 0) {
                        value--;
                        rt.add(ent.getKey());
                    }
                    return rt.stream();
                }).map(String::valueOf)
                .collect(Collectors.toList());
    }

    private static Map<Character, Long> toMap(char[] chars) {
        List<Character> lst = charArrayToList(chars);
        return lst.stream().collect(Collectors.groupingBy(Function.identity(), Collectors.counting()));
    }

    private static List<Character> charArrayToList(char[] chars) {
        List<Character> lst = new ArrayList<>(chars.length);
        for (char c : chars) {
            lst.add(c);
        }
        return lst;
    }

    public static void main(String[] args) {
//        String s = addBinary("11", "1");
//        System.out.println(s);
        int[] nums = {2,1,4,7,3,2,5};
        System.out.println(longestMountain(nums));
    }


    /**
     * 845. 数组中的最长山脉
     * 比上一个大 上坡
     * 比上一个小  下坡
     * 上坡+下坡是一个山脉
     *
     * @param arr
     * @return
     */
    public static int longestMountain(int[] arr) {
        int maxLen = 0;
        LinkedList<Integer> stk = new LinkedList<>();
        stk.addLast(arr[0]);
        int up = 0;
        for (int i = 1; i < arr.length; i++) {
            int val = arr[i];
            Integer last = stk.peekLast();
            if (val > last) {
                if (up == 2) {
                    int size = stk.size();
                    if (size > maxLen) {
                        maxLen = size;
                    }
                    stk.clear();
                    stk.add(last);
                }
                stk.addLast(val);
                up = 1;
            } else if (val == last) {
                // 冲突、 清零
                if (up == 2) {
                    int size = stk.size();
                    if (size > maxLen) {
                        maxLen = size;
                    }
                }
                stk.clear();
                stk.add(val);
                up = 1;
            } else {
                if (up == 1) {
                    up = 2;
                }
                if (up == 0) {
                    stk.clear();
                }
                stk.addLast(val);
            }
        }
        if (up == 2 && !stk.isEmpty()) {
            int size = stk.size();
            if (size > maxLen) {
                maxLen = size;
            }
        }
        return maxLen;
    }
}
